﻿// 0826train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <map>
#include <deque>

using namespace std;

/*
 给定一个 m x n 二维字符网格 board 和一个字符串单词 word
 如果 word 存在于网格中，返回 true ；否则，返回 false 
单词必须按照字母顺序，通过相邻的单元格内的字母构成，
其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
同一个单元格内的字母不允许被重复使用

输入：board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
word = "ABCCED"
输出：true
 */
class Solution01 {
public:
    void backTrack(
        vector<vector<char>>&board, 
        vector<vector<bool>>&checked,
        string&word,
        int prev_r, int prev_c
    )
    {
        if (search_pos>=word.size())
        {
            is_find = true;
            return;
        }

        for (auto&dir_vec:DirectionGrid)
        {
            int curr_r = prev_r + dir_vec[0];
            int curr_c = prev_c + dir_vec[1];

            bool is_curr_r = curr_r >= 0 && curr_r < row_size;
            bool is_curr_c = curr_c >= 0 && curr_c < col_size;

            if (!is_curr_r || !is_curr_c) continue;

            bool is_visited = checked[curr_r][curr_c];
            char search_char = word[search_pos];
            bool is_available = board[curr_r][curr_c] == search_char;

            if (is_available && !is_visited)
            {
                search_pos += 1;
                checked[curr_r][curr_c] = true;
                backTrack(board, checked, word, curr_r, curr_c);
                search_pos -= 1;
                checked[curr_r][curr_c] = false;
            }

        }


        //backTrack
    }

    bool exist(vector<vector<char>>& board, string word) {
        row_size = board.size();
        col_size = board[0].size();

        //checked DirectionGrid
        vector<bool>check_status(col_size, false);
        vector<vector<bool>>checked(row_size, check_status);

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                //未访问 可到达
                char search_char = word[search_pos];
                bool is_visited = checked[r][c];
                bool is_available = board[r][c] == search_char;

                if (is_available && !is_visited)
                {
                    search_pos += 1;
                    checked[r][c] = true;
                    backTrack(board, checked, word, r, c);
                    search_pos -= 1;
                    checked[r][c] = false;
                }

                if (is_find) return true;

                //col_size
            }

            //row_size
        }
        return false;

    }
private:
    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,1},{0,-1}};
    int row_size = 0, col_size = 0;
    int search_pos = 0; //待寻找的位置
    bool is_find = false;
};


/*
 给你一个整数 n ，表示编号从 1 到 n 的 n 门课程
 另给你一个数组 relations ，其中 relations[i] = [prevCoursei, nextCoursei] ，
 表示课程 prevCoursei 和课程 nextCoursei 之间存在先修关系：
 课程 prevCoursei 必须在 nextCoursei 之前修读完成

在一个学期内，你可以学习 任意数量 的课程，但前提是你已经在上一学期修读完待学习课程的所有先修课程
请你返回学完全部课程所需的最少学期数
如果没有办法做到学完全部这些课程的话，就返回 -1

bfs最短路径

输入：n = 3, relations = [[1,3],[2,3]]
输出：2
 */

class Solution02 {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        //map<int,vector<int>>linked_map
        //入度map
        map<int, vector<int>>linked_map;
        map<int, int>indegree_map;

        //初始化indegree_map
        for (int i=1;i<=n;i++)
        {
            indegree_map[i] = 0;
        }

        //relations[i] = [prevCoursei, nextCoursei]
        //prev->next
        for (auto&min_vec:relations)
        {
            int start = min_vec[0];
            int arrive = min_vec[1];

            linked_map[start].push_back(arrive);
            indegree_map[arrive] += 1;
        }

        deque<int>bfs_queue;
        //入度为0，进bfs
        for (auto&map_item:indegree_map)
        {
	        if (map_item.second==0)
	        {
                bfs_queue.push_back(map_item.first);
	        }
        }

        int curr_count = 0;
        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();
            curr_count += 1;
            for (int i=0; i<q_size; i++)
            {
                int top_node = bfs_queue.front();
                bfs_queue.pop_front();

                vector<int>curr_vec = linked_map[top_node];
                for (auto&node:curr_vec)
                {
                    //更新入度表
                    indegree_map[node] -= 1;
                    //入度为0进bfs
                    if (indegree_map[node]==0)
                    {
                        bfs_queue.push_back(node);
                    }
                }
            }
            //while (!bfs_queue.empty())
        }

        for (auto&map_item:indegree_map)
        {
            if (map_item.second!=0)
            {
                return -1;
            }
        }
        return curr_count;
        //入度为0，进bfs_queue
    }
};


/*
 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），
 矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）
 同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol]
 表示你一开始所在格子的行和列

每一步操作，你可以往 上，下，左 或者 右 移动一个格子
你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口
出口的含义是 maze 边界上的空格子
entrance 格子不算出口

返回从 entrance 到最近出口的最短路径的步数 ，如果不存在这样的路径，请你返回-1

输入：
maze = [
["+","+",".","+"],
[".",".",".","+"],
["+","+","+","."]
],
entrance = [1,2]
输出：
1

 */

class Solution03 {
public:
    bool checkOut(vector<int>& entrance, int row, int col)
    {
        //出口的含义是 maze 边界上的空格子
        //entrance 格子不算出口
        if (row==entrance[0]&&col==entrance[1])
        {
            return false;
        }
        if (row==0 || row== row_size-1 || col==0 || col==col_size-1)
        {
            return true;
        }
        return false;
    }

    void bfsUpdate(vector<vector<char>>& maze,
        vector<int>& entrance,
        vector<vector<bool>>checked,
        deque<pair<int, int>>bfs_queue

    )
    {
        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();
            curr_count += 1;

            //层序遍历
            for (int i = 0; i < q_size; i++)
            {
                pair<int, int>top_node = bfs_queue.front();
                bfs_queue.pop_front();

                for (auto& dir_vec : DirectionGrid)
                {
                    int curr_r = top_node.first + dir_vec[0];
                    int curr_c = top_node.second + dir_vec[1];

                    bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                    bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                    if (is_curr_r && is_curr_c)
                    {
                        bool is_visited = checked[curr_r][curr_c];
                        //空格子（用 '.' 表示）
                        bool is_available = maze[curr_r][curr_c] == '.';

                        if (is_available && !is_visited)
                        {
                            if (checkOut(entrance, curr_r, curr_c))
                            {
                                is_find = true;
                                //找到出口直接return
                                return;
                            }

                            bfs_queue.push_back(make_pair(curr_r, curr_c));
                            checked[curr_r][curr_c] = true;
                        }

                    }

                    //DirectionGrid
                }

            }
            //while (!bfs_queue.empty())
        }
    }

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        //checked DirectionGrid bfs_queue
        row_size = maze.size();
        col_size = maze[0].size();

        vector<bool>checked_status(col_size, false);
        vector<vector<bool>>checked(row_size, checked_status);

        deque<pair<int, int>>bfs_queue;
        bfs_queue.push_back(make_pair(entrance[0],entrance[1]));
        //标记已访问
        checked[entrance[0]][entrance[1]] = true;

        bfsUpdate(maze, entrance, checked, bfs_queue);
        
        if (is_find) return curr_count;

        return -1;

        //nearestExit
    }

private:
    vector<vector<int>>DirectionGrid = {{-1,0},{1,0},{0,-1},{0,1}};
    int row_size = 0, col_size = 0;
    int curr_count = 0;
    bool is_find = false;
};

int main()
{
	{
/*
[["+",".","+","+","+","+","+"],
["+",".","+",".",".",".","+"],
["+",".","+",".","+",".","+"],
["+",".",".",".","+",".","+"],
["+","+","+","+","+","+","."]]
entrance = [0,1]
*/
        vector<vector<string>>maze_str = {
        	{"+",".","+","+","+","+","+"},
        	{"+",".","+",".",".",".","+"},
        	{"+",".","+",".","+",".","+"},
            {"+",".",".",".","+",".","+"},
            {"+","+","+","+","+","+","."},
        };
        vector<vector<char>>maze;
        for (auto&min_vec: maze_str)
        {
            vector<char>min_char;
            for (auto&oh_str:min_vec)
            {
                min_char.push_back(oh_str[0]);
            }
            maze.push_back(min_char);
        }

        vector<int>entrance = { 0,1 };
        Solution03 solu;
        cout << solu.nearestExit(maze, entrance);

        return 0;
	}
/*
输入：n = 3, relations = [[1,3],[2,3]]
输出：2

输入：n = 3, relations = [[1,2],[2,3],[3,1]]
输出：-1
*/
	{
        int n = 3;
        vector<vector<int>>relations = {{1,3},{2,3},{3,1}};
        Solution02 solu;
        cout << solu.minimumSemesters(n, relations);

        return 0;
	}
/*
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
],
word = "ABCCED"
*/
    vector<vector<char>>board = { {'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'} };
    string word = "ABCCED";
    Solution01 solu;
    cout << solu.exist(board, word);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
